Algorithms

Communication 1

As of yesterday, 34 people have subscribed to the Telegram group

Please subscribe to the Telegram group as soon as possible

Invitation link to join the group:
https://t.me/joinchat/GrGmRRWkB6PqyuFPxRMovQ

Communication 2

Exam sessions dates:

  • 29 January 2021

  • 15 March 2021

  • 17 May 2021

  • 14 June 2021

  • 12 July 2021

  • 20 September 2021

For each date:

  • written examination: 9-11

  • project oral colloquium: 11-16

Communication 3

You can format the various comments you write in the issue tab on GitHub by using Markdown

Instructions at https://guides.github.com/features/mastering-markdown/

Any question about the previous lecture?

Historic hero: Ada Lovelace

English mathematicians

English translator of the first article about Babbage's Analytical Engine, written by Luigi Federico Menabrea in French

She enriched the English translation of the article with several annotations

Original article: ~8000 words

Notes by Ada: additional ~19000 words

Ada's heritage

First mechanical computer programmer: in the article notes, there is a description of how to use the Analytical Engine to calculate the Bernoulli numbers

The operating mechanism can even be thrown into action independently of any object to operate upon (although of course no result could then be developed). Again, it might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine. Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.

Science of Operations = Computer Science

Common features

What do recipes and instructions for assembling objects have in common?

Shared abstract notion: step-by-step procedure for producing something starting from some initial material we have = algorithm

Algorithm

The word algorithm is a combination of the Latin word algorismus (that is the Latinization of the name Al-Khwarizmi, who was a great mathematician from Persia in the 8th century) and the Greek word arithmos, meaning number

Each algorithm is written in a specific language which is functional to communicate its instruction to a computer

Computer programmer: anyone that creates algorithms that can be interpreted by any computer

Pseudocode

Pseudocode in an informal language that could be interpreted easily by any computer - even if, usually, it is pretty close to a programming language

It is used by computer scientists for sketching an algorithm before to implement it in a particular programming language

Checking if an algorithm can be interpretable by a computer: provide a colleague with pseudocode of the algorithm and ask her to execute it using a particular input, writing down all the passages of the execution on a piece of paper

Flowchart

In this lecture, though, we use a particular graphical alternative to common pseudocode which is good for being understandable by humans: a flowchart

[Our first algorithm] Consider three different strings as input, i.e. two words and a bibliographic entry of a published paper. The algorithm must return: the number 2 if the bibliographic entry contains both words; the number 1 if the bibliographic entry contains only one word; the number 0 otherwise.

E.g.: input "Berners-Lee", "web" and "Tim Berners-Lee: Designing the web for an open society. WWW 2011: 3-4"; output 2.

Flowchart: flowline

The arrow is used to define the order in which the operations are executed

The flow indicated by the arrows begin in the starting terminal and ends in the ending terminal

Flowchart: terminal

It indicates the beginning and ending of an algorithm

It contains a text (usually, either "start" or "end") so as to disambiguate which role has the particular terminal widget in the context of the algorithm

Flowchart: input / output

It allows one to specify possible input / output material which is used / returned by the algorithm usually at the beginning or end of its execution

Flowchart: decision

It depicts a conditional operation, where a condition is checked and, depending on the value of some of the variables involved in the algorithm, the execution continues in a particular branch instead of another

Usually, the this operation creates two possible alternative branches: one to be followed whether the condition considered is true, and the other in case the condition is false

Partial algorithm

Consider two different strings as input, i.e. a words and a bibliographic entry of a published paper, and return 1 if the bibliographic entry contains the word, 0 otherwise

Partial algorithm

Take in input only two strings, i.e. an input word and a bibliographic entry, and return 1 if the the input word is contained in the bibliographic entry, otherwise return 0

Partial algorithm

Take in input only two strings, i.e. an input word and a bibliographic entry, and return 1 if the the input word is contained in the bibliographic entry, otherwise return 0

Partial algorithm

Take in input only two strings, i.e. an input word and a bibliographic entry, and return 1 if the the input word is contained in the bibliographic entry, otherwise return 0

Partial algorithm

Take in input only two strings, i.e. an input word and a bibliographic entry, and return 1 if the the input word is contained in the bibliographic entry, otherwise return 0

Flowchart: process

It is used for expressing (usually one) instruction or operation, that is executed and that can change the current state of some variables used in the algorithm

The text it includes depicts the instruction to execute

Final algorithm: reprise

Consider three different strings as input, i.e. two words and a bibliographic entry of a published paper. The algorithm must return: the number 2 if the bibliographic entry contains both words; the number 1 if the bibliographic entry contains only one word; the number 0 otherwise

Final algorithm: flowchart

Final algorithm: flowchart

Final algorithm: flowchart

Final algorithm: flowchart

Final algorithm: flowchart

Final algorithm: flowchart

Final algorithm: flowchart

Final algorithm: flowchart

Final algorithm: flowchart

How to create flowcharts

Old-fashioned method: use a piece of paper plus either a pencil or pen - it works, I swear

Modern method: there exists also online tools that allow you to create a flowchart by using an (electronic) computer - e.g. the one that has been used to create all the diagrams in this lecture is called Diagrams.net, which is a free-to-use Web application with a nice graphical user interface

END Algorithms